package com.sheng.leetcode.year2023.month03.day17;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2023/03/17
 * <p>
 * 2389. 和有限的最长子序列<p>
 * <p>
 * 给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。<p>
 * 返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度  。<p>
 * 子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [4,5,2,1], queries = [3,10,21]<p>
 * 输出：[2,3,4]<p>
 * 解释：queries 对应的 answer 如下：<p>
 * - 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ，所以 answer[0] = 2 。<p>
 * - 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ，所以 answer[1] = 3 。<p>
 * - 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ，所以 answer[2] = 4 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [2,3,4,5], queries = [1]<p>
 * 输出：[0]<p>
 * 解释：空子序列是唯一一个满足元素和小于或等于 1 的子序列，所以 answer[0] = 0 。<p>
 * <p>
 * 提示：<p>
 * n == nums.length<p>
 * m == queries.length<p>
 * 1 <= n, m <= 1000<p>
 * 1 <= nums[i], queries[i] <= 10^6<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/longest-subsequence-with-limited-sum">2389. 和有限的最长子序列</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode2389 {

    @Test
    public void test01() {
        int[] nums = {4, 5, 2, 1}, queries = {3, 10, 21};
//        int[] nums = {2,3,4,5}, queries = {1};
        System.out.println(Arrays.toString(new Solution().answerQueries(nums, queries)));
    }
}

class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        int n = nums.length;
        int m = queries.length;
        int[] answer = new int[m];
        // 数组 nums 的总和
        int sum = Arrays.stream(nums).sum();
        // 对数组进行排序
        Arrays.sort(nums);
        for (int i = 0; i < m; i++) {
            int j = n - 1;
            int k = sum;
            // 如果总和大于，那么减去数组中最大的数
            while (k > queries[i]) {
                k -= nums[j--];
            }
            answer[i] = j + 1;
        }
        return answer;
    }
}
